from typing import List
class Solution:
    def integer_replacement(self, n: int) -> int:
        count = 0
        while n > 1:
            if n & 1 == 0:  # n 为偶数
                n >>= 1  # 相当于 n = n // 2
            elif n & 3 == 3 and n != 3:  # n 除以 4 余数为 3
                n += 1
            else:
                n -= 1
            count += 1
        return count

    def solve_n_queens(self, n: int) -> list[list[str]]:
        def backtrack(row: int) -> None:
            if row == n:
                # 找到一组解法，保存到数组中
                res.append([''.join(row) for row in board])
                return

            for col in range(n):
                if not cols[col] and not diag1[row + col] and not diag2[row - col]:
                    # 如果当前位置可以放置皇后
                    board[row][col] = 'Q'
                    cols[col] = True
                    diag1[row + col] = True
                    diag2[row - col] = True

                    # 递归到下一行
                    backtrack(row + 1)

                    # 回溯
                    board[row][col] = '.'
                    cols[col] = False
                    diag1[row + col] = False
                    diag2[row - col] = False

        res = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        cols = [False] * n
        diag1 = [False] * (2 * n - 1)
        diag2 = [False] * (2 * n - 1)
        backtrack(0)
        return res

    def max_sub_array(self, nums: list[int]) -> int:
        # 初始化变量
        max_sum = current_sum = nums[0]

        # 遍历数组
        for i in range(1, len(nums)):
            # 更新当前子数组的最大和
            current_sum = max(nums[i], current_sum + nums[i])
            # 更新全局最大和
            max_sum = max(max_sum, current_sum)

        return max_sum

    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int] 
        :type nums2: List[int]    
        :type k: int 
        :rtype: List[int] 
        """
        m, n = len(nums1), len(nums2)
        res = []
        # 从 nums1 和 nums2 的长度中选出可以组成 k 个数的长度，这样不会遗漏
        for i in range(max(0, k-n), min(k, m)+1): # 保证返回值res是k的长度
            left = self.max_num(nums1, i) # 从 nums1 中筛选出长度为 i 的子串
            right = self.max_num(nums2, k-i) # 从 nums2 中筛选出长度为 k-i 的子串
            tmp = self.merge_nums(left, right) # 逐个比较元素来合并两个数组
            # 更新最大子集的值
            if not res or self.compare_nums(tmp, 0, res, 0) > 0:
                res = tmp
        return res
    
    def max_num(self,nums, k):
        stack = []
        drop = len(nums) - k # 需要弹出的元素个数
        for num in nums:
            # 如果添加当前的 num 的话，会使 stack[-1] 小于 num，因此将 stack[-1] 弹出
            while drop and stack and stack[-1] < num:
                stack.pop()
                drop -= 1
            stack.append(num)
        return stack[:k] # 返回将需要弹出元素去除的结果 

    def merge_nums(self,nums1, nums2):
        res = []
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            if self.compare_nums(nums1, i, nums2, j) > 0:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1
        res += nums1[i:] # 将剩余的 nums1 数组放入返回值的末尾
        res += nums2[j:] # 将剩余的 nums2 数组放入返回值的末尾
        return res

    def compare_nums(self,nums1, i, nums2, j):
        """
        比较 nums1 和 nums2 两个数组中从 i 和 j 开始的元素的大小
        如果 nums1[i:] > nums2[j:], 即 nums1 从 i 开始的元素比 nums2 从 j 开始的元素更大，返回正数
        如果 nums1[i:] == nums2[j:], 即 nums1 从 i 开始的元素等于 nums2 从 j 开始的元素，返回 0
        如果 nums1[i:] < nums2[j:], 即 nums1 从 i 开始的元素比 nums2 从 j 开始的元素更小，返回负数
        """
        while i < len(nums1) and j < len(nums2):
            diff = nums1[i] - nums2[j]
            if diff != 0:
                return diff
            i += 1
            j += 1
        return (len(nums1)-i) - (len(nums2)-j)
    

    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res =[[nums[0]]]
        for i in range(1,len(nums)):
            tmp = []
            for j in range(len(res)):
                for k in range(len(res[j])+1):
                    tmp.append(res[j][:k]+[nums[i]]+res[j][k:])
            res = tmp
        return res
    
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        tree_path = []
        if root is not None:
            self.dfs(root, [], tree_path)
        return tree_path
        
    def dfs(self, root, path, tree_path):
        path.append(str(root.val))
        if root.left is None and root.right is None:
            tree_path.append("->".join(path))
        if root.left:
            self.dfs(root.left, path, tree_path)
        if root.right:
            self.dfs(root.right, path, tree_path)
        path.pop()
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        stack = []
        remove = len(s) - k
        remainder = s.count(letter)
        for ch in s:
            while remove and stack and ch < stack[-1]:
                if stack[-1] == letter and remainder == repetition: break
                if stack.pop() == letter: remainder -= 1
                remove -= 1
            stack.append(ch)
        stack = stack[:k]
        cur = stack.count(letter)
        if cur < repetition:
            for i in range(k - 1, -1, -1):
                if cur == repetition: break
                if stack[i] != letter:
                    stack[i] = letter
                    cur += 1
        return "".join(stack)

    def maxProfit(self, prices) -> int:

        n = len(prices)

        dp0, dp1 = 0, -prices[0]  # 初始化
        for i in range(1, n):
            dp0, dp1 = max(dp0, dp1 + prices[i]), max(dp1, dp0 - prices[i])

    def first_missing_positive(self, nums: list[int]) -> int:
        n = len(nums)
        seen = set(nums)  # 将所有出现的正整数加入哈希表中

        # 从 1 开始递增，每次检查该数字是否在哈希表中出现，如果没有出现就返回该数字
        for i in range(1, n + 1):
            if i not in seen:
                return i

        # 如果所有正整数都出现过，那么缺失的就是 n+1
        return n + 1

    def pathWithObstacles(self, obstacleGrid):
        ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])

        def f(path):
            if not ans:
                i, j = path[-1]
                if not obstacleGrid[i][j]:
                    obstacleGrid[i][j] = 1
                    i < r - 1 and f(path + [[i + 1, j]])
                    j < c - 1 and f(path + [[i, j + 1]])
                    if (i, j) == (r - 1, c - 1):
                        ans.extend(path)

        f([[0, 0]])
        return ans
# 分治算法 位一个数
    def hammingWeight(self, n) :
        res = n.count('1')
        return res
    # 组合总和 回溯 动态规划
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 递归函数 回溯
        def backtrack(start, path, total):
            # 等于 弹出并返回
            if total == target:
                res.append(path[:])
                return
            # 大于 返回
            if total > target:
                return
            # 小于 尝试调用所有数组元素
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(i, path, total + candidates[i])
                path.pop()

        # 返回数组定义为空
        res = []
        candidates.sort()
        backtrack(0, [], 0)
        return res
    # 分发糖果贪心算法
    def candy(self, ratings: List[int]) -> int:
        # 初始化
        n = len(ratings)
        left_to_right = [1] * n
        right_to_left = [1] * n

        # 从左到右计算结点最小值
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                left_to_right[i] = left_to_right[i-1] + 1

        # 从右到左计算结点最小值
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                right_to_left[i] = right_to_left[i+1] + 1

        # 每个节点取最大值即是该节点最少分配到的糖果
        return sum(max(left_to_right[i], right_to_left[i]) for i in range(n))